Almost every company has a large amount of confidential data used in business in a computer system. Such data are important in conducting business and, moreover, must not be leaked outside by any means from a perspective of personal information protection. Therefore, while data encryption is required for a business system to be newly constructed as a matter of course, an existing business system that does not support encryption is also demanded to have an additional function for storing data with encryption.
However, in an existing business system, a data format is often determined in advance. For example, a credit card number is one of typical examples of serious personal information with high necessity of protection, for which a data format of “decimal 16 digits” is defined in advance. In an existing business system, data other than the defined format is often treated as an error and not able to be processed. The same goes to a telephone number, a postal code, a bank account number, and the like.
Thus, required is an encryption method in which a data format of a plain text matches a data format of a cipher text that is encrypted therefrom. Such an encryption method is referred to as format-preserving encryption. Likewise, a decryption method in which a data format of a cipher text matches a data format of a plain text is referred to as format-preserving decryption. Utilizing the format-preserving encryption/decryption, a data encryption/decryption function can be added to an existing business system with a minimum change to the system.
In a general encryption method (block cipher), messages (a plain text and a cipher text) are expressed in binary spaces of the same format. For example, messages of Data Encryption Standard (DES) and Advanced Encryption Standard (AES), as known encryption methods, are respectively 64 bits and 128 bits. On the contrary, the format-preserving encryption deals with data such as “64-bit or less binary space” and “non-binary space (for example, decimal, or a combination of binary and decimal).”
Such a format-preserving encryption is disclosed, for example, in the following technical literature. NPL1 is an article that popularized the name of format-preserving encryption across the world. NPL2 describes Knuth Shuffle, also known as Fisher-Yates Shuffle, as a method of realizing a safe block cipher, in principle, in any message spaces. However, the calculation amount and memory amount are in a linear order to a message space, whereby the amount of processing tends to be vast. Thus, Knuth Shuffle is difficult to be applied to a message space of more than 10,000 in size.
NPL3 describes a block cipher that specifically deals with a case where messages are in a decimal space. NPL4 describes attacks to the cipher method of NPL3.
NPL5 describes a method of realizing a block cipher in a binary space or non-binary space of n-bit or less using an n-bit block cipher. The method described in NLP5 causes a problem in which the method is efficient and secure when a size of the target message space is slightly smaller than 2n, while either efficiency or security significantly decreases when the size becomes smaller than 2n by a certain amount.
In the same way as NPL5, NPL6 also describes a method in which permutation processing called Feistel permutation is realized using a block cipher and encryption is performed by repeating this permutation processing on a plain text for a predetermined number of times. The above-described NPL1 also describes the same method.
FIG. 6 is an explanatory diagram illustrating an overview of the encryption method described in NPL6. FIG. 6 illustrates processing for one cycle of permutation processing. Having Xm+1, . . . , Xd, a round counter ctr, an external tweak gt, and the number of digits of a plain text d as input values, an AES encryptor 901 outputs an encrypted value (128 bits) by encrypting the input values by an AES encryption method. A modulo 902 outputs a remainder of division of the output value from the AES encryptor 901 by a^m (m power of a). An adder 903 outputs a value obtained by adding X1, . . . , Xm and the output value from the modulo 902. Then, after replacing the output from the adder 903 with Xm+1, . . . , Xd, one cycle of the permutation processing completes. This processing is repeated for a predetermined number of times.
NPL7 describes a tweakable block cipher that is a block cipher method using an auxiliary parameter called tweak for encryption and decryption. NPL8 and 9 describe block ciphers in a variety of message spaces that are realized utilizing the tweakable block cipher. These methods can guarantee relatively high efficiency and security when the tweakable block cipher is secure.
Further, there is also described a method of realizing a tweakable block cipher of n-bit block based on an n-bit block cipher. Therefore, a method of creating a 2n-bit block cipher based on an n-bit block cipher can be obtained from the method described in NPL8, and a method of creating an n+1-bit or more block cipher based on an n-bit block cipher can be obtained from the method described in NPL9.
According to the methods described in NPL8 and 9, depending on a parameter, format-preserving encryption can be realized with higher efficiency and security than a method combining Feistel permutation and a block cipher as described in NPL1 and 6. NPL10 to 13 will be described later herein.
PTL1 describes a technique for protecting data stored in a database from traffic analysis. PTL2 describes a technique for changing a character set of data stored in a database to obfuscate the data. PTL3 to 4 describe a block encryption method that utilizes an external tweak (an adjustment value), which are patent applications corresponding to the above-described NPL8 and 9. PTL5 describes a technique for performing encryption while maintaining a format of an MPEG4 file.